package cn.edu.jxau.test;

import java.util.Arrays;

import javax.xml.stream.util.EventReaderDelegate;

import cn.edu.jxau.util.LinkedStack;
import cn.edu.jxau.util.Stack;

/**
 * Dijkstra算法的原始实现
 * 
 * @author 付大石
 */
public class Dijkstra {

    public static void main(String[] args) {

        DirectedGraph g = new DirectedGraph(8);
        g.addEdge(new DirectedEdge(4, 5, 0.35));
        g.addEdge(new DirectedEdge(5, 4, 0.35));
        g.addEdge(new DirectedEdge(4, 7, 0.37));
        g.addEdge(new DirectedEdge(5, 7, 0.28));
        g.addEdge(new DirectedEdge(7, 5, 0.28));
        g.addEdge(new DirectedEdge(5, 1, 0.32));
        g.addEdge(new DirectedEdge(0, 4, 0.38));
        g.addEdge(new DirectedEdge(0, 2, 0.26));
        g.addEdge(new DirectedEdge(7, 3, 0.39));
        g.addEdge(new DirectedEdge(1, 3, 0.29));
        g.addEdge(new DirectedEdge(2, 7, 0.34));
        g.addEdge(new DirectedEdge(6, 2, 0.40));
        g.addEdge(new DirectedEdge(3, 6, 0.52));
        g.addEdge(new DirectedEdge(6, 0, 0.58));
        g.addEdge(new DirectedEdge(6, 4, 0.93));
        System.out.println(g);
        int s = 0;
        Dijkstra spt = new Dijkstra(g, s);
        for (int v = 0; v < g.v(); v++) {
            if (spt.hasPathTo(v)) {
                System.out.printf("%d to %d:", s, v);
                for (DirectedEdge edge : spt.pathTo(v)) {
                    System.out.printf("%d->%d(%.2f)\t", edge.from(), edge.to(), edge.weight());
                }
                System.out.println();
            } else {
                System.out.println("没有到达" + v + "的路径");
            }
        }
    }

    /**
     * 标记是否已进入SPT
     */
    private boolean[] marked;

    /**
     * 起点到某点的最短距离,比如distTo[i]就表示起点到顶点i的距离。
     * 起点到起点的距离为0。
     */
    private double[] distTo;

    /**
     * 存储路径信息
     */
    private DirectedEdge[] edgeTo;

    public Dijkstra(DirectedGraph g, int s) {

        // 参数校验 //
        if (s < 0 || s >= g.v()) {
            throw new IllegalArgumentException("图中不存在顶点s=" + s);
        }

        // 初始化数据域 //
        marked = new boolean[g.v()];
        edgeTo = new DirectedEdge[g.v()];
        distTo = new double[g.v()];
        Arrays.fill(distTo, Double.POSITIVE_INFINITY);

        // 预处理//
        distTo[s] = 0;
        edgeTo[s] = null;

        // 开始构造shortest path tree //
        for (int i = 0; i < g.v() - 1; i++) {
            int minIndex = 0;
            double min = Double.POSITIVE_INFINITY;
            for (int j = 0; j < distTo.length; j++) { // 找出未被确定的，最小的路径
                if (!marked[j]) {
                    if (distTo[j] < min) {
                        min = distTo[j];
                        minIndex = j;
                    }
                }
            }
            relax(g, minIndex);
        }
    }

    /**
     * 由于顶点from的加入，一方面，起点可能可以到达更多的顶点，所以需要更新distTo数组
     * 另一方面起点到以前已经可达的顶点的路径可能会减小，所以也需要更新distTo数组。
     * @param g
     * @param from
     */
    private void relax(DirectedGraph g, int from) {

        marked[from] = true;
        for (DirectedEdge edge : g.adj(from)) {
            int to = edge.to();
            if (distTo[to] > distTo[from] + edge.weight()) {
                distTo[to] = distTo[from] + edge.weight();
                edgeTo[to] = edge;
            }
        }
    }

    public double distTo(int to) {
        return distTo[to];
    }

    public boolean hasPathTo(int to) {
        return distTo[to] < Double.POSITIVE_INFINITY;
    }

    public Iterable<DirectedEdge> pathTo(int to) {

        Stack<DirectedEdge> path = new LinkedStack<>();
        if (!hasPathTo(to)) {
            return path;
        }
        while (edgeTo[to] != null) {
            path.push(edgeTo[to]);
            to = edgeTo[to].from();
        }
        return path;
    }
}
